/*
* Copyright (c) 2007 by Kirill Kolodyazhniy.
* See the file "license.terms" for information on usage and redistribution.
*/

#ifndef M_LFQUEUE_H
#define M_LFQUEUE_H

#include "lfprimitives.h"
#ifdef _MSC_VER
#pragma warning(disable: 4127) // conditional expression is constant
#endif

namespace Engine
{
	namespace LockFree
	{
		/**
		*   Class implement queue container with lock free synchronization.
		*/
		template<typename T>
		class Queue
		{
		public:
			/**
			*   Constructor.
			*   @param pDummy dummy head node - required for algorithm.
			*/
			Queue(node<T>* pDummy) : m_cPops(0), m_cPushes(0)
			{
				m_pHead = m_pTail = pDummy;
			}

			/**
			*   Add new node to end of queue.
			*/
			void Add(node<T>* pNode);

			/**
			*   Retrieve and remove from container head node.
			*/
			node<T>* Remove();

			/**
			*   Retrieve and remove from container last(dummy) node.
			*   May use for clearing queue.
			*/
			node<T>* GetHead();

			/**
			*   Return true if queue empty.
			*/
			bool Empty() const;

		private:
			// NOTE: the order of these members is assumed by CAS2.
			node<T> * volatile m_pHead;   ///< pointer to head node.
			volatile uint32_t  m_cPops;   ///< count of add calls.
			node<T> * volatile m_pTail;   ///< pointer to last node.
			volatile uint32_t  m_cPushes; ///< count of remove call.
		};
		/*************************************************************************************************/
		template<typename T>
		void Queue<T>::Add(node<T> * pNode)
		{
			pNode->pNext = 0;

			uint32_t cPushes;
			node<T> * pTail;

			while(true)
			{
				cPushes = m_cPushes;
				pTail = m_pTail;

				if(CAS(&(m_pTail->pNext), reinterpret_cast<node<T> *>(0), pNode))
				{
					break;
				}
				else
				{
					CAS2(&m_pTail, pTail, cPushes, m_pTail->pNext, cPushes + 1);
				}
			}

			CAS2(&m_pTail, pTail, cPushes, pNode, cPushes + 1);
		}
		/*************************************************************************************************/
		template<typename T>
		node<T> * Queue<T>::Remove()
		{
			T value = T();
			node<T> * pHead;

			while(true)
			{
				uint32_t cPops = m_cPops;
				uint32_t cPushes = m_cPushes;
				pHead = m_pHead;
				node<T> * pNext = pHead->pNext;

				if(cPops != m_cPops)
				{
					continue;
				}
				// Check if the queue is empty.
				if(pHead == m_pTail)
				{
					if(0 == pNext)
					{
						pHead = 0; // queue is empty
						break;
					}
					// Special case if the queue has nodes but the tail
					// is just behind. Move the tail off of the head.
					CAS2(&m_pTail, pHead, cPushes, pNext, cPushes + 1);
				}
				else if(0 != pNext)
				{
					value = pNext->value;
					// Move the head pointer, effectively removing the node
					if(CAS2(&m_pHead, pHead, cPops, pNext, cPops + 1))
					{
						break;
					}
				}
			}
			if(0 != pHead)
			{
				pHead->value = value;
			}
			return pHead;
		}
		/*************************************************************************************************/
		template<typename T>
		node<T>* Queue<T>::GetHead()
		{
			return m_pHead;
		}
		/*************************************************************************************************/
		template<typename T>
		bool Queue<T>::Empty() const
		{
			return m_pHead == m_pTail;
		}
		/*************************************************************************************************/
	}
}
#endif
